#include <iostream>
using namespace std;
#define maxsize 1000
typedef struct node
{
    int data[maxsize];
    int front, rear;
}Queue,*LQnode;

void chushiqueue(Queue &Q)//初始化队列
{
    Q.data[0] = 1;
    Q.data[1] = 0;
    Q.front = 0;
    Q.rear = 2;
}

//利用公式a[i][j]=a[i-1][j-1]+a[i-1][j]。在每一行行尾插入0（第48行代码）作为换行标识
void creatqueue(Queue &Q,int n)//创建杨辉三角对应队列并打印
{
    if((Q.rear+1)%maxsize==Q.front)
    {
        cout << "队列满";
        return;
    }
    int i, k, x, y;//x=a[i-1][j-1],  y=a[i-1][j]
    x = 0;
    i = 0;
    while (i < n)
    {
        for (k = 1; k <= n - i - 1; k++)//输出空格使打印出正三角形
        {
            cout << "  ";
        }
        do
        {
            y = Q.data[Q.front];//取队首元素
            Q.data[Q.rear] = x + y; // a[i][j]插入队列
            Q.front = (Q.front + 1) % maxsize;//队首出队
            Q.rear = (Q.rear + 1) % maxsize;
            x = y; // x后移，存上一个队首元素
            if(y!=0)
            printf("%2d  ", y);//格式化输出对齐三角形
        } while (y != 0);
        if(y==0)//可以不需要判断，此时y=0
        {
            i++;//从第0行开始，行数+1
            Q.data[Q.rear] = 0;//入队0，意味着a[i][j]所在行结束
            Q.rear = (Q.rear + 1) % maxsize;
            cout << endl;//换行
        }
    }
}

int main()
{
    Queue Q;
    int n;
    chushiqueue(Q);
    cin >> n;
    creatqueue(Q, n);
    return 0;
}
